#pragma once

#include <bits/stdc++.h>
using namespace  std;
template <class T>
struct BSTNode
{
    BSTNode(const T &x = T())
    :data(x)
    ,left(nullptr)
    ,right(nullptr)
    {}
    T data;
    BSTNode<T> *left, *right;
};


template<class T>
class BSTree
{
    private:
        typedef BSTNode<T> Node;
        Node *root;
    public:
    BSTree()
    :root(nullptr)
    {

    }
    bool insert(const T& data)
    {
        if(root==nullptr)
        {
            root = new Node;
            root->data = data;
            return true;
        }
        Node *curNode = root;
        while(curNode!=nullptr)
        {
            if(data<curNode->data)
            {
                if(curNode->left==nullptr)
                {
                    curNode->left = new Node;
                    curNode->left->data = data;
                    return true;
                }
                curNode = curNode->left;
            }
            else if(data>curNode->data)
            {
                if(curNode->right==nullptr)
                {
                    curNode->right = new Node;
                    curNode->right->data = data;
                    return true;
                }
                curNode = curNode->right;
            }
            else
            {
                curNode = nullptr;
                break;
            }

        }
        return false;
    }

    vector<T> inorderTraversal()//non-cursion ,记录走过的节点
        //基本思维先访问的父节点，后出，决定栈的性质，但是出了父节点，就要考虑右节点，所以单独处理
        {
            vector<T> result;
            if(root==nullptr)
            {
                return result;
            }
            stack<Node*> nodestack;
            Node* temp = root;//我们认为这个是存的第一次访问的指针，后续在此访问一定就是从栈顶
            while(!nodestack.empty() || temp)
            {
                while(temp)
                {
                    nodestack.push(temp);
                    temp = temp->left;
                }
                if(nodestack.size())
                {
                    result.push_back(nodestack.top()->data);
                    temp = nodestack.top()->right;//是空上面也进不去，就会继续出栈元素
                    nodestack.pop();
                }
            }
            return result;
        }
    vector<T> PostOrderTraversal()//non-cursion 头结点先进出利用栈的思维即可
    {
        vector<T> result;
        if(root==nullptr)
        {
            return result;
        }
        stack<Node*> nodestack;
        nodestack.push(root);
        vector<bool> flagstack(1,true);
        Node* leftnode = root->left;
        while(nodestack.size() || leftnode)
        {
            while(leftnode)
            {
                nodestack.push(leftnode);
                flagstack.push_back(true);
                leftnode = leftnode->left;
            }
            if(nodestack.size())
            {
                if(flagstack.back())
                {
                    flagstack.back() = false;
                    leftnode = nodestack.top()->right;
                }
                else
                {
                    flagstack.pop_back();
                    result.push_back(nodestack.top()->data);
                    nodestack.pop();
                }
            }
        }
        return result;
    }
    Node* findParent(const T& data,int &left)const
    {
        if(root==nullptr)
        {
            return nullptr;
        }
        Node* curnode = root;
        Node* parent = root;
        while(curnode!=nullptr)
        {
            if(curnode->data>data)
            {
                parent = curnode;
                curnode = curnode->left;
                left = 1;
            }
            else if(curnode->data<data)
            {
                parent = curnode;
                curnode = curnode->right;
                left=0;
            }
            else
            {
                if(curnode==root)
                {
                    left = -1;
                }
                return parent;
            }
        }
        return nullptr;
    }
    Node* find(const T& data)const
    {
        if(root==nullptr)
        {
            return nullptr;
        }
        Node* curnode = root;
        while(curnode!=nullptr)
        {   
            if(curnode->data>data)
            {
                curnode = curnode->left;
            }
            else if(curnode->data<data)
            {
                curnode = curnode->right;
            }
            else
            {
                return curnode;
            }
        }
        return nullptr;
    }
    bool erase(const T&data)
    {
        Node* parent = root;
        Node* curnode = root;
        while(curnode)
        {
            if(curnode->data>data)
            {
                parent = curnode;
                curnode = curnode->left;
            }
            else if(curnode->data<data)
            {
                parent = curnode;
                curnode = curnode->right;
            }
            else//开始删除
            {
                if(curnode->left==nullptr)
                {
                    if(curnode==root)
                    {
                        root=curnode->right;
                    }
                    else
                    {
                        if(parent->left==curnode)
                        {
                            parent->left = curnode->right;

                        }
                        else
                        {
                            parent->right = curnode->right;
                        }
                    }
                }
                else if(curnode->right==nullptr)
                {
                    if(curnode==root)
                    {
                        root=curnode->left;
                    }
                    else
                    {
                        if(parent->left==curnode)
                        {
                            parent->left = curnode->left;
                        }
                        else
                        {
                            parent->right = curnode->left;
                        }
                    }
                }
                else
                {
                    Node* ChildLeft = curnode->right;
                    parent = curnode;
                    while(ChildLeft->left)
                    {
                        parent = ChildLeft;
                        ChildLeft = ChildLeft->left;
                    }
                    swap(ChildLeft->data,curnode->data);
                    if(ChildLeft==parent->left)
                    {
                        parent->left = ChildLeft->right;
                    }
                    else
                    {
                        parent->right = ChildLeft->right;
                    }
                    delete ChildLeft;
                    ChildLeft = nullptr;
                }
                
                return 1;
            }
        }
        return 0;
    }
    Node* findR(const T& data)
    {
        return mp_findR(data,root);
    }
    
    bool insertR(const T& data)
    {
        if(root==nullptr)
        {
            root = new Node(data);
            return true;
        }
        return mp_insertR(data,root);
    }
    bool eraseR(const T& data)
    {
        int left = -1;
        if(root==nullptr)
        {
            return 1;
        }
        Node* curnode = root;
        Node* parent = root;
        while(curnode!=nullptr)
        {
            if(curnode->data>data)
            {
                parent = curnode;
                curnode = curnode->left;
                left = 1;
            }
            else if(curnode->data<data)
            {
                parent = curnode;
                curnode = curnode->right;
                left=0;
            }
            else
            {
                if(curnode==root)
                {
                    left = -1;
                }
                break;
            }
        }
        if(left==-1)
        {
            return mp_eraseR(root);
        }
        else if(left==1)
        {
            return mp_eraseR(parent->left);
        }
        return mp_eraseR(parent->right);
    }
    ~BSTree()
    {
        if(root==nullptr)
        {
            return result;
        }
        list<Node*> nodelist(1,root);
        while(nodelist.size())
        {
            Node* temp = nodelist.front();
            nodelist.pop_front();
            result.push_back(temp->data);
            if(temp->right)
            {
                nodelist.push_front(temp->right);
            }
            if(temp->left)
            {  
                nodelist.push_front(temp->left);
            }
            delete temp;
        }
        root = nullptr;
    }
    private:
        Node* Copy(Node* Eroot)
        {
            if(Eroot==nullptr)
            {
                return nullptr;
            }
            list<Node*> nodelist(1,Eroot);
            Node* ROOT = new Node(Eroot->data);
            list<Node*> newlist(1,ROOT);
            Node* newnode = nullptr;
            while(nodelist.size()){

                Node* curnode = nodelist.front();
                nodelist.pop_front();
                Node* NowCopiedNode = newlist.front();
                newlist.pop_front();

                if(curnode->left!=nullptr)
                {
                    nodelist.push_back(curnode->left);
                    Node* newleft = new Node(curnode->left->data);
                    NowCopiedNode->left = newleft;
                    newlist.push_back(newleft);

                }
                if(curnode->right!=nullptr)
                {
                    nodelist.push_back(curnode->right);
                    Node* newright = new Node(curnode->right->data);
                    NowCopiedNode->right = newright;
                    newlist.push_back(newright);
                }
            }
            return ROOT;
        }
        Node* Copy_R(Node* Eroot)
        {
            if(Eroot==nullptr)
            {
                return nullptr;
            }
            Node* ROOT = new Node(Eroot->data);
            ROOT->left = Copy_R(Eroot->left);
            ROOT->right = Copy_R(Eroot->right);
            return  ROOT;
        }
        Node* mp_findR(const T& data,Node* Eroot)
        {
            if(Eroot==nullptr)
            {
                return nullptr;
            }
            if(Eroot->data==data)
            {
                return Eroot;
            }
            else if(root->data>data)
            {
                return mp_findR(data,Eroot->left);
            }
            else{
                return mp_findR(data,Eroot->right);
            }
        }
        bool mp_insertR(const T& data,Node* Eroot)
        {
            if(Eroot==nullptr)
            {
                return false;
            }
            if(Eroot->data>data)
            {
                if(Eroot->left==nullptr)
                {
                    Eroot->left = new Node(data);
                    return true;
                }
                else
                {
                    return mp_insertR(data,Eroot->left);
                }
            }
            else
            {
                if(Eroot->right==nullptr)
                {
                    Eroot->right = new Node(data);
                    return true;
                }
                else
                {
                    return mp_insertR(data,Eroot->right);
                }
            }
        }
        bool mp_eraseR(Node* &Eroot)
        {
            if(Eroot==nullptr)
            {
                return false;
            }
            else if(Eroot->left==nullptr)
            {
                Node* del = Eroot;
                Eroot = Eroot->right;
                delete del;
                return 1;
            }
            else if(Eroot->right==nullptr)
            {
                Node* del = Eroot;
                Eroot = Eroot->left;
                delete del;
                return 1;
            }
            else
            {
                Node* Childleft = Eroot->right;
                Node* parent = Eroot;
                while(Childleft->left!=nullptr)
                {
                    parent = Childleft;
                    Childleft = Childleft->left;
                }
                swap(root->data,Childleft->data);
                if(Childleft==parent->left)
                {
                    mp_eraseR(parent->left);//需要该改变的是父类里面那个存的指针的值
                }
                else
                {
                    mp_eraseR(parent->right);
                }
            }
            return true;
        }
};